package com.lili.sort;

import java.util.concurrent.ThreadLocalRandom;

/**
 * @Auther: 李 力
 * @Date: 2024/8/2
 * @Description: 双边快排
 * @version: 1.0
 */
public class BilateralSort {

    /*
     * 时间复杂度: 最好O(nlogn)  最坏O(n^2)  平均O(logn)
     * 空间复杂度: O(logn)
     */
    public static int[] bilateralSort(int[] arr) {
        sort(arr, 0, arr.length - 1);
        return arr;
    }

    private static void sort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(arr, left, right);
        sort(arr, left, p - 1);
        sort(arr, p + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {
        //优化:随机元素作为基准点元素
        int rand = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(arr, rand, left);
        int pv = arr[left];
        int i = left + 1;
        int j = right;
        //优化:有大量重复的元素
        while (i <= j) {
            //j从右向左找小的
            while (i <= j && arr[i] < pv) {
                i++;
            }
            //i从左向右找大的
            while (i <= j && arr[j] > pv) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        swap(arr, j, left);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
